#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5 + 10;
const int M = (1 << 15);
int n, C, Q, A[N], F[N];
int fa[N], sz[N]; int Find(int x) { return (fa[x] == x ? x : fa[x] = Find(fa[x])); };
void merge(int u, int v) {
	if (u == v) return ;
	if (sz[u] < sz[v]) swap(u, v);
	sz[u] += sz[v]; sz[v] = 0; fa[v] = u; return ;
}
namespace Part1 {
void Solve() {
	int x, y;
	while (Q --) {
		cin >> x >> y;
		for (int i = 1; i <= n; i ++) fa[i] = i, sz[i] = 1;
		for (int i = 2; i <= n; i ++) if (((x >> A[i]) & 1) && ((x >> A[F[i]]) & 1))
			merge(Find(i), Find(F[i]));
		cout << sz[Find(y)] << "\n";
	} return ;
}

}
namespace Part2 {
int Ans[N];
vector<pair<int, int> > qry[M];
void Solve() {
	for (int i = 1, u, v; i <= Q; i ++) {
		cin >> u >> v; qry[u].emplace_back(make_pair(v, i));
	}
	for (int sta = 0; sta < (1 << C); sta ++) if (!qry[sta].empty()) {
		for (int i = 1; i <= n; i ++) fa[i] = i, sz[i] = 1;
		for (int i = 2; i <= n; i ++) if (((sta >> A[i]) & 1) && ((sta >> A[F[i]]) & 1))
			merge(Find(i), Find(F[i]));
		for (auto it : qry[sta]) { int u = it.first, v = it.second; Ans[v] = sz[Find(u)]; }
	}
	for (int i = 1; i <= Q; i ++) cout << Ans[i] << "\n";
	return ;
}

}
namespace Part3 {
vector<pair<int, int> > qry[N]; int fst[N], lst[N], id[N];
void Solve() {
	for (int i = 1, u, v; i <= Q; i ++) {
		cin >> u >> v; qry[v].emplace_back(make_pair(u, i)); 
	}
	for (int i = 0; i < C; i ++) id[i] = 0;
	for (int i = 1; i <= n; i ++) {
		id[A[i]] = i;
		for (auto it : qry[i]) {
			int u = it.first, v = it.second;
			int mx = 1;
			for (int j = 0; j < C; j ++) if (!((u >> j) & 1))
				mx = max(mx, id[j] + 1);
			fst[v] = min(mx, i);
		}
	}
	for (int i = 0; i < C; i ++) id[i] = n + 1;
	for (int i = n; i >= 1; i --) {
		id[A[i]] = i;
		for (auto it : qry[i]) {
			int u = it.first, v = it.second;
			int mn = n;
			for (int j = 0; j < C; j ++) if (!((u >> j) & 1))
				mn = min(mn, id[j] - 1);
			lst[v] = max(mn, i);
		}
	}
	for (int i = 1; i <= Q; i ++) cout << lst[i] - fst[i] + 1 << "\n";
}

}

int main(){
	freopen("tree.in", "r", stdin); freopen("tree.out", "w", stdout);
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> Q >> C; fa[1] = 1;
	for (int i = 1; i <= n; i ++) cin >> A[i];
	for (int i = 2; i <= n; i ++) cin >> F[i];
	if (n <= 5000 && Q <= 5000) Part1::Solve();
	else if (C <= 10) Part2 :: Solve();
	else Part3 :: Solve();
	return 0;
}